package com.lw.leetcode.arr.c;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 2503. 矩阵查询可获得的最大分数
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/12 13:44
 */
public class MaxPoints2503 {

    public static void main(String[] args) {
        MaxPoints2503 test = new MaxPoints2503();

        // {5,8,1}
//        int[][] grid = {{1, 2, 3}, {2, 5, 7}, {3, 5, 1}};
//        int[] queries = {5, 6, 2};

        // {0}
        int[][] grid = {{5, 2, 1}, {1, 1, 2}};
        int[] queries = {3};

        int[] ints = test.maxPoints(grid, queries);
        System.out.println(Arrays.toString(ints));
    }

    private int[][] grid;
    private int m;
    private int n;
    private int count = 0;
    private int[][] items = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int[] maxPoints(int[][] grid, int[] queries) {
        int length = queries.length;
        this.m = grid.length;
        this.n = grid[0].length;
        this.grid = grid;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < length; i++) {
            map.computeIfAbsent(queries[i], v -> new ArrayList<>()).add(i);
        }
        Arrays.sort(queries);
        List<Long> list = new ArrayList<>();
        int[] values = new int[length];
        list.add((long) grid[0][0]);
        for (int query : queries) {
            List<Long> all = new ArrayList<>();
            for (long v : list) {
                int x = (int) (v >> 48);
                int y = (int) ((v >> 32) & 0XFFFF);
                int value = (int) v;
                find(query, x, y, value, all);
            }
            list = all;
            List<Integer> li = map.get(query);
            for (Integer index : li) {
                values[index] = count;
            }
        }
        return values;
    }

    private void find(int t, int x, int y, int value, List<Long> list) {
        if (grid[x][y] == 0) {
            return;
        }
        if (value >= t) {
            list.add(value + ((long) x << 48) + ((long) y << 32));
            return;
        }
        grid[x][y] = 0;
        count++;
        for (int[] item : items) {
            int a = x + item[0];
            int b = y + item[1];
            if (a < 0 || b < 0 || a == m || b == n || grid[a][b] == 0) {
                continue;
            }
            find(t, a, b, grid[a][b], list);
        }
    }

}
